package com.lun.other.tree;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class BinaryTreeTraversal {
	
	/**
	 * 递归版前序遍历
	 * 
	 * @param root
	 */
	public static String recursivePreorderTraverse(TreeNode root) {
		if(root == null) return "";
		StringBuilder sb = new StringBuilder();
		recursivePreorderTraverse(root, sb);
		return sb.substring(0, sb.length() - 1);
	}

	private static void recursivePreorderTraverse(TreeNode node, StringBuilder sb) {
		if (node == null)
			return;
		print(node, sb);
		recursivePreorderTraverse(node.left, sb);
		recursivePreorderTraverse(node.right, sb);
	}
	
	/**
	 * 迭代版前序遍历
	 * 
	 * @param root
	 * @return
	 */
	public static String iterativePreorderTraverse(TreeNode root) {
	
		if(root == null)
			return "";
		
		StringBuilder sb = new StringBuilder();
		LinkedList<TreeNode> stack = new LinkedList<>();
		stack.push(root);
		
		while(!stack.isEmpty()) {
			TreeNode node = stack.pop();
			print(node, sb);
			
			//right child is pushed first so that left is processed first
			if(node.right != null)
				stack.push(node.right);
			
			if(node.left != null)
				stack.push(node.left);
		}
		
		return sb.substring(0, sb.length() - 1);
	}

	/**
	 * 递归版中序遍历
	 * 
	 * @param root
	 * @return
	 */
	public static String recursiveInorderTraverse(TreeNode root) {
		if(root == null) return "";
		StringBuilder sb = new StringBuilder();
		recursiveInorderTraverse(root, sb);
		return sb.substring(0, sb.length() - 1);
	}

	private static void recursiveInorderTraverse(TreeNode node, StringBuilder sb) {
		if (node == null)
			return;
		recursiveInorderTraverse(node.left, sb);
		print(node, sb);
		recursiveInorderTraverse(node.right, sb);
	}
	
	/**
	 * 迭代版中序遍历
	 * 
	 * @param root
	 * @return
	 */
	public static String iterativeInorderTraverse(TreeNode root) {
		if(root == null) return "";
		StringBuilder sb = new StringBuilder();
		LinkedList<TreeNode> stack = new LinkedList<>();
		TreeNode p = root;

		while(!stack.isEmpty() || p != null) {
			
			if(p != null) {
				stack.push(p);
				p = p.left;
			}else {
				p = stack.pop();
				print(p, sb);
				p = p.right;
			}
		}		
		return sb.substring(0, sb.length() - 1);
	}
	

	/**
	 * 递归版后序遍历
	 * 
	 * @param root
	 * @return
	 */
	public static String recursivePostorderTraverse(TreeNode root) {
		if(root == null) return "";
		StringBuilder sb = new StringBuilder();
		recursivePostorderTraverse(root, sb);
		return sb.substring(0, sb.length() - 1);
	}
	
	public static void recursivePostorderTraverse(TreeNode node, StringBuilder sb) {
		if (node == null)
			return;
		recursivePostorderTraverse(node.left, sb);
		recursivePostorderTraverse(node.right, sb);
		print(node, sb);
	}
	
	/**
	 * 迭代版后序遍历
	 * 
	 * @param root
	 * @return
	 */
	public static String iterativePostorderTraverse(TreeNode root) {
		if(root == null) return "";
		StringBuilder sb = new StringBuilder();
		LinkedList<TreeNode> stack = new LinkedList<>();
		TreeNode p = root, lastNodeVisited = null;
		while(!stack.isEmpty() || p != null) {
			if(p != null) {
				stack.push(p);
				p = p.left;
			}else {
				TreeNode peekNode = stack.peek();
				if(peekNode.right != null && lastNodeVisited != peekNode.right) {
					p = peekNode.right;
				}else {
					print(peekNode, sb);
					lastNodeVisited = stack.pop();
				}
			}
		}
		return sb.substring(0, sb.length() - 1);
	}

	/**
	 * 按层遍历
	 * 
	 * @return
	 */
	public static String levelOrderTraverse(TreeNode root) {
		if(root == null) return "";
		StringBuilder sb = new StringBuilder();
		LinkedList<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()) {
			TreeNode node = queue.poll();
			print(node, sb);
			if(node.left != null)
				queue.offer(node.left);
			if(node.right != null)
				queue.offer(node.right);
		}
		return sb.substring(0, sb.length() - 1);
	}
	
	
	private static void print(TreeNode node, StringBuilder sb) {
		sb.append(node.val);
		sb.append(',');
	}
}
